#include <dbg.h>
#include <gtest/gtest.h>

using namespace std;

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        dfs(root, 0, res);
        return res;
    }

private:
    void dfs(TreeNode* root, int depth, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        if (depth == res.size()) {  // 每一层只记录一个节点
            res.push_back(root->val);
        }
        dfs(root->right,
            depth + 1,
            res);  // 先遍历右子树,
                   // 这样就可以保证每一层的第一个节点就是最右边的节点
        dfs(root->left, depth + 1, res);
    }
};

TEST(rightSideView, TestCase1) {
    Solution s;

    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(4);
    root->left->right = new TreeNode(5);

    vector<int> ans = {1, 3, 4};
    EXPECT_EQ(s.rightSideView(root), ans);
}

TEST(rightSideView, TestCase2) {
    Solution s;

    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->left->left = new TreeNode(5);

    vector<int> ans = {1, 3, 4, 5};
    EXPECT_EQ(s.rightSideView(root), ans);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}